package com.LeeCode;

import java.util.List;

/**
 * 破解锁的最少时间 I
 */

public class Code3376 {
    public static void main(String[] args) {

    }

    public int findMinimumTime(List<Integer> strength, int k) {
        boolean[] done = new boolean[strength.size()];
        dfs(0, 0, strength.toArray(Integer[]::new), k, done);
        return ans;
    }

    private int ans = Integer.MAX_VALUE;

    private void dfs(int i, int time, Integer[] strength, int k, boolean[] done) {
        // 剪枝：答案不可能变小
        if (time >= ans) {
            return;
        }
        if (i == strength.length) {
            ans = time;
            return;
        }
        int x = 1 + k * i;
        for (int j = 0; j < strength.length; j++) {
            if (!done[j]) {
                done[j] = true; // 已开锁
                dfs(i + 1, time + (strength[j] + x - 1) / x, strength, k, done);
                done[j] = false; // 恢复现场
            }
        }
    }
}
